import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author LKQ
 * @date 2021/11/28 18:49
 * @description
 */
public class Solution1 {
    public static void main(String[] args) {
        Solution1 solution1 = new Solution1();
        System.out.println(solution1.isValid("(([]){})"));
    }
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            // 奇数个括号肯定错误
            return false;
        }
        Stack<String> stack = new Stack<>();
        Map<String, String> pairs = new HashMap<String, String>() {{
            put(")", "(");
            put("]", "[");
            put("}", "{");
        }};
        int count = 0;
        for (int i = 0; i < n; i++) {
            String temp = s.substring(i,i+1);
            if ("(".equals(temp) || "[".equals(temp) || "{".equals(temp)) {
                stack.push(temp);
            }else {
                if (stack.empty()) {
                    // 栈中没有左括号进入，而右括号来了，字符串无效。
                    break;
                } else if (pairs.get(temp).equals(stack.pop())) {
                    count++;
                }
            }
        }
        return count == n/2;
    }

}
